package com.yaoli.ajob;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by siemens on 4/5/2017.
 */
public class _451_SortCharactersByFrequency {
    public static void main(String[] args) {
        _451_SortCharactersByFrequency a = new _451_SortCharactersByFrequency();

        a.frequencySort("Tree");
    }

    public String frequencySort(String s) {
        char [] ss = s.toCharArray();

        //List<Map<Character,Integer>> [] set = new ArrayList<Map<>> [s.length() - 1];
        Map<Character,Integer> [] set = new HashMap [s.length()];


        Map<Character,Integer> map = new HashMap<>();

        for(int i = 0 ; i < s.length() ; i ++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }

        for(char c : map.keySet()){
            Integer number = map.get(c);

            if(set[number - 1] == null){
                set[number - 1] = new HashMap<>();
            }

            set[number - 1].put(c,number);
        }

        StringBuilder res = new StringBuilder("");

        for(int i = set.length - 1 ; i>=0 ;i--){
            if(set[i] != null){
                for(char c : set[i].keySet()){
                    int num = set[i].get(c);
                    for(int j = 0 ; j < num ; j++){
                        res.append(c);
                    }
                }
            }
        }

        return res.toString();


    }
}
